package SortAlgorithm;

import org.junit.Test;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 10:00 2021/3/9
 * @Description： 归并排序
 */
public class MergeSort {
    void mergeSort(int[] arr) {
        // 分配一个辅助数组
        int[] tempArr = new int[arr.length];

        msort(arr, tempArr, 0, arr.length - 1);
    }

    void msort(int[] arr, int[] tempArr, int start, int end) {
        // 递归结束条件，序列中只剩一个元素，本身就是有序的
        if (start < end) {
            // 找到中间索引位置，继续递归划分左右序列
            int mid = (start + end) >> 1;
            // 递归划分左半区域
            msort(arr, tempArr, start, mid);
            // 递归划分右半区域
            msort(arr, tempArr, mid + 1, end);

            // 合并左右区域
            merge(arr, tempArr, start, mid, end);
        }
    }

    void merge(int[] arr, int[] tempArr, int start, int mid, int end) {
        // 标志左半区域第一个未排序的元素
        int l_pos = start;
        // 标记右半区第一个未排序的元素
        int r_pos = mid + 1;
        // 标记临时数组的下标
        int pos = start;

        // 合并
        while (l_pos <= mid && r_pos <= end) {
            if (arr[l_pos] <= arr[r_pos]) {// 左半区域第一个剩余元素更小
                tempArr[pos] = arr[l_pos];
                l_pos++;
            } else { // 右半区域第一个剩余第一个元素更小
                tempArr[pos] = arr[r_pos];
                r_pos++;
            }
            pos++;
        }

        // 合并左半区域剩余的元素，显然有序
        while (l_pos <= mid) {
            tempArr[pos] = arr[l_pos];
            l_pos++;
            pos++;
        }

        // 合并右半区剩余的元素
        while (r_pos <= end) {
            tempArr[pos] = arr[r_pos];
            r_pos++;
            pos++;
        }

        // 把临时数组中排序的元素复制到原来的数组
        while (start <= end) {
            arr[start] = tempArr[start];
            start++;
        }
    }

    @Test
    public void test(){
        int[] testArray = {5, 8, 4, 6, 7, 2, 1, 10};

        mergeSort(testArray);

        for(int i :testArray){
            System.out.print(i+",");
        }
    }
}
